//Given an m x n matrix, return all elements of the matrix in spiral order. 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[1,2,3],
//                 [4,5,6],
//                 [7,8,9]]
//Output: [1,2,3,6,9,8,7,4,5]
// 
//
// Example 2: 
//
// 
//Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
//Output: [1,2,3,4,8,12,11,10,9,5,6,7]
// 
//
// 
// Constraints: 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 10 
// -100 <= matrix[i][j] <= 100 
// 
// Related Topics 数组 
// 👍 775 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;

//Java：Spiral Matrix
 class P54SpiralMatrix{
    public static void main(String[] args) {
        Solution solution = new P54SpiralMatrix().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public  ArrayList<Integer> spiralOrder(int[][] matrix) {
            ArrayList<Integer> res = new ArrayList<>();
            if (matrix == null || matrix.length == 0) {
                return res;
            }
            int colStart = 0, colEnd = matrix[0].length - 1;
            int rowStart = 0, rowEnd = matrix.length - 1;
            while (colStart <= colEnd && rowStart <= rowEnd) {
                //对外圈进行处理
                //第一行
                for (int j = colStart; j <= colEnd; j++) {
                    res.add(matrix[rowStart][j]);
                }
                //最后一列
                for (int i = rowStart + 1; i <= rowEnd; i++) {
                    res.add(matrix[i][colEnd]);
                }
                //最后一行
                for (int j = colEnd - 1; j >= colStart && rowEnd != rowStart; j--) {
                    res.add(matrix[rowEnd][j]);
                }
                //第一列
                for (int i = rowEnd - 1; i >= rowStart + 1 && colStart != colEnd; i--) {
                    res.add(matrix[i][colStart]);
                }
                colStart++;
                colEnd--;
                rowStart++;
                rowEnd--;
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}